package bin_tree.leetcode;

/**
 * 判断子树问题
 * @author yuisama
 * @date 2022/02/20 15:08
 **/
public class Num572_SubTree {
    /**
     * 传入两颗树root和subRoot，就能判断出subRoot是否是root的子树
     * @param root
     * @param subRoot
     * @return
     */
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        // 边界
        if (root == null && subRoot == null) {
            return true;
        }
        if (root == null || subRoot == null) {
            return false;
        }
        // root和subRoot相同 || 左树包含 || 右树包含
        return isSameTree(root,subRoot) || isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 边界条件
        if (p == null && q == null) {
            // 两棵树都是空树
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        return p.val == q.val &&
                isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
}